// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package types

import (
	"go/ast"
	"go/token"
)

// 此文件执行一项检查，以验证Go包是否没有无限递归实例化
// 这与使用静态实例化（例如
// 单态化）的编译器不兼容。
// 
// 它通过检测哪些
// 类型参数与其他类型参数（或其派生的
// 类型）实例化，来实现一种“类型流”分析。如果图中有至少一个派生类型的任何循环，则不能静态实例化包
// 。具体地说，我们构造了一个有向加权图。顶点是
// 用于表示类型参数以及一些定义的
// 类型。边用于表示类型之间的相互依赖关系：
// 
// *只要实例化了类型参数化的函数或类型，
// 我们就从顶点向每个类型参数添加边（如果有）
// 表示
// 类型参数引用的每个类型参数或定义的类型。如果type参数只是被引用的
// 类型本身，那么边的权重为0，否则为1。
// 
// *对于在类型参数化
// 函数或方法中声明的每个已定义类型，我们从每个环境类型参数向已定义的
// 类型添加权重为1的边。
// 
// 例如，给定：
// 
// func f[A，B any]（{
// typet int-
// f[T，map[A]B]（）
// }
// 我们构造表示类型A、B和T的顶点。因为
// 权重1构造边T<-A和T<-B；由于实例化“f[T，map[A]B]”，我们构造了
// 边A<-T的权重为0，边B<-A和边B<-B的权重为1。
// 
// 最后，我们寻找任何正权重周期。由于静态实例化将达到一个固定点，因此允许零权重循环
// 。

type monoGraph struct {
	vertices []monoVertex
	edges    []monoEdge

	// 佳能将方法接收器类型参数映射到各自的
	// 接收器类型的类型参数。
	canon map[*TypeParam]*TypeParam

	// nameIdx将定义的类型或（规范的）类型参数映射到其
	// 顶点索引。
	nameIdx map[*TypeName]int
}

type monoVertex struct {
	weight int // 到该顶点的已知最重路径的权重
	pre    int // 上述路径中的前一条边
	len    int // 上述路径的长度

	// obj是由该
	// 顶点表示的定义类型或类型参数。
	obj *TypeName
}

type monoEdge struct {
	dst, src int
	weight   int

	pos token.Pos
	typ Type
}

func (check *Checker) monomorph() {
	// 我们使用
	// Bellman Ford算法的一个变体来检测无界实例化周期。也就是说，我们不是一直运行|V | 
	// 迭代，而是一直运行，直到到达一个固定点，或者找到一条长度为|V |的路径。这使我们可以在没有周期时提前终止
	// 这应该是常见的情况。

	again := true
	for again {
		again = false

		for i, edge := range check.mono.edges {
			src := &check.mono.vertices[edge.src]
			dst := &check.mono.vertices[edge.dst]

			// N.B.，我们正在寻找最大的重量路径，不同于典型的贝尔曼福特。
			w := src.weight + edge.weight
			if w <= dst.weight {
				continue
			}

			dst.pre = i
			dst.len = src.len + 1
			if dst.len == len(check.mono.vertices) {
				check.reportInstanceLoop(edge.dst)
				return
			}

			dst.weight = w
			again = true
		}
	}
}

func (check *Checker) reportInstanceLoop(v int) {
	var stack []int
	seen := make([]bool, len(check.mono.vertices))

	// 我们有一条路径，它包含一个循环并以v结束，但是v可能只能从循环中到达，而不能在循环本身上到达。我们沿着路径向后走，直到找到一个出现两次的顶点。
	for !seen[v] {
		stack = append(stack, v)
		seen[v] = true
		v = check.mono.edges[check.mono.vertices[v].pre].src
	}

	// 在第一次访问v之前修剪我们访问过的所有顶点。因为v是我们在循环中找到的第一个顶点，所以我们之前访问过的任何
	// 顶点都不能是循环的一部分。
	for stack[0] != v {
		stack = stack[1:]
	}

	// TODO（mdempsky）：轴心堆栈，所以我们从顶部报告周期？

	obj0 := check.mono.vertices[v].obj
	check.errorf(obj0, _InvalidInstanceCycle, "instantiation cycle:")

	qf := RelativeTo(check.pkg)
	for _, v := range stack {
		edge := check.mono.edges[check.mono.vertices[v].pre]
		obj := check.mono.vertices[edge.dst].obj

		switch obj.Type().(type) {
		default:
			panic("unexpected type")
		case *Named:
			check.errorf(atPos(edge.pos), _InvalidInstanceCycle, "\t%s implicitly parameterized by %s", obj.Name(), TypeString(edge.typ, qf)) // 次要错误，\t缩进的
		case *TypeParam:
			check.errorf(atPos(edge.pos), _InvalidInstanceCycle, "\t%s instantiated as %s", obj.Name(), TypeString(edge.typ, qf)) // 次要错误，\t缩进的
		}
	}
}

// recordCanon记录tpar是与方法类型参数mpar相对应的规范类型参数
// 。
func (w *monoGraph) recordCanon(mpar, tpar *TypeParam) {
	if w.canon == nil {
		w.canon = make(map[*TypeParam]*TypeParam)
	}
	w.canon[mpar] = tpar
}

// recordInstance记录给定的类型参数是
// 用相应的类型参数实例化。
func (w *monoGraph) recordInstance(pkg *Package, pos token.Pos, tparams []*TypeParam, targs []Type, xlist []ast.Expr) {
	for i, tpar := range tparams {
		pos := pos
		if i < len(xlist) {
			pos = xlist[i].Pos()
		}
		w.assign(pkg, pos, tpar, targs[i])
	}
}

// 分配tpar在pos处被实例化为targ的记录。
func (w *monoGraph) assign(pkg *Package, pos token.Pos, tpar *TypeParam, targ Type) {
	// Go泛型与C++的模板模板没有类似之处，
	// 其中模板参数本身可以是可实例化的
	// 模板。因此，任何实例化周期都必须发生在单个
	// 包中。因此，我们可以忽略导入的
	// 类型参数。
	// 
	// TODO（mdempsky）：将此检查推到recordInstance中？列表中的所有类型
	// 参数将出现在同一个包中。
	if tpar.Obj().Pkg() != pkg {
		return
	}

	// flow从顶点src添加一条边，表示该类型流到tpar。
	flow := func(src int, typ Type) {
		weight := 1
		if typ == targ {
			weight = 0
		}

		w.addEdge(w.typeParamVertex(tpar), src, weight, pos, targ)
	}

	// 递归遍历类型参数，以查找任何已定义的类型或
	// 类型参数。
	var do func(typ Type)
	do = func(typ Type) {
		switch typ := typ.(type) {
		default:
			panic("unexpected type")

		case *TypeParam:
			assert(typ.Obj().Pkg() == pkg)
			flow(w.typeParamVertex(typ), typ)

		case *Named:
			if src := w.localNamedVertex(pkg, typ.Origin()); src >= 0 {
				flow(src, typ)
			}

			targs := typ.TypeArgs()
			for i := 0; i < targs.Len(); i++ {
				do(targs.At(i))
			}

		case *Array:
			do(typ.Elem())
		case *Basic:
			// ok 
		case *Chan:
			do(typ.Elem())
		case *Map:
			do(typ.Key())
			do(typ.Elem())
		case *Pointer:
			do(typ.Elem())
		case *Slice:
			do(typ.Elem())

		case *Interface:
			for i := 0; i < typ.NumMethods(); i++ {
				do(typ.Method(i).Type())
			}
		case *Signature:
			tuple := func(tup *Tuple) {
				for i := 0; i < tup.Len(); i++ {
					do(tup.At(i).Type())
				}
			}
			tuple(typ.Params())
			tuple(typ.Results())
		case *Struct:
			for i := 0; i < typ.NumFields(); i++ {
				do(typ.Field(i).Type())
			}
		}
	}
	do(targ)
}

// localNamedVertex返回表示
// named的顶点的索引，如果named不需要表示，则返回-1。
func (w *monoGraph) localNamedVertex(pkg *Package, named *Named) int {
	obj := named.Obj()
	if obj.Pkg() != pkg {
		return -1 // 导入的类型
	}

	root := pkg.Scope()
	if obj.Parent() == root {
		return -1 // 包作用域，无环境类型参数
	}

	if idx, ok := w.nameIdx[obj]; ok {
		return idx
	}

	idx := -1

	// 遍历类型定义的作用域以查找其隐式参数化的任何环境类型
	// 参数。
	for scope := obj.Parent(); scope != root; scope = scope.Parent() {
		for _, elem := range scope.elems {
			if elem, ok := elem.(*TypeName); ok && !elem.IsAlias() && elem.Pos() < obj.Pos() {
				if tpar, ok := elem.Type().(*TypeParam); ok {
					if idx < 0 {
						idx = len(w.vertices)
						w.vertices = append(w.vertices, monoVertex{obj: obj})
					}

					w.addEdge(idx, w.typeParamVertex(tpar), 1, obj.Pos(), tpar)
				}
			}
		}
	}

	if w.nameIdx == nil {
		w.nameIdx = make(map[*TypeName]int)
	}
	w.nameIdx[obj] = idx
	return idx
}

// typeParamVertex返回表示tpar的顶点的索引。
func (w *monoGraph) typeParamVertex(tpar *TypeParam) int {
	if x, ok := w.canon[tpar]; ok {
		tpar = x
	}

	obj := tpar.Obj()

	if idx, ok := w.nameIdx[obj]; ok {
		return idx
	}

	if w.nameIdx == nil {
		w.nameIdx = make(map[*TypeName]int)
	}

	idx := len(w.vertices)
	w.vertices = append(w.vertices, monoVertex{obj: obj})
	w.nameIdx[obj] = idx
	return idx
}

func (w *monoGraph) addEdge(dst, src, weight int, pos token.Pos, typ Type) {
	// TODO（mdempsky）：重复数据消除冗余边缘？
	w.edges = append(w.edges, monoEdge{
		dst:    dst,
		src:    src,
		weight: weight,

		pos: pos,
		typ: typ,
	})
}
